//给你两个数组，arr1 和 arr2， 
//
// 
// arr2 中的元素各不相同 
// arr2 中的每个元素都出现在 arr1 中 
// 
//
// 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末
//尾。 
//
// 
//
// 示例： 
//
// 
//输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
//输出：[2,2,2,1,4,3,3,9,6,7,19]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= arr1.length, arr2.length <= 1000 
// 0 <= arr1[i], arr2[i] <= 1000 
// arr2 中的元素 arr2[i] 各不相同 
// arr2 中的每个元素 arr2[i] 都出现在 arr1 中 
// 
// Related Topics 数组 哈希表 计数排序 排序 
// 👍 180 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] ans = new int[arr1.length];
        int index = 0;
        int[] temp = new int[arr1.length];
        for (int i = 0; i < temp.length; i++) {
            temp[i] = 0;
        }

        for (int i = 0; i < arr2.length; i++) {
            for (int j = 0; j < arr1.length; j++) {
                if (arr1[j] == arr2[i]) {
                    ans[index++] = arr1[j];
                    temp[j] = 1;
                }
            }
        }

        int numsLen = arr1.length - index;
        int[] nums = new int[numsLen];

        int numsIndex = 0;
        for (int i = 0; i < arr1.length; i++) {
            if (temp[i] == 0) {
                nums[numsIndex++] = arr1[i];
            }
        }
        sortTemp = new int[numsLen];
        mergeSort(nums, 0, numsLen - 1);

        for (int i = 0; i < nums.length; i++) {
            ans[index++] = nums[i];
        }

        return ans;
    }

    int[] sortTemp;

    public void mergeSort(int[] nums, int l, int r) {
        if (r <= l) {
            return;
        }
        if (l+1 == r) {
            if (nums[l] > nums[r]) {
                int sortTemp = nums[l];
                nums[l] = nums[r];
                nums[r] = sortTemp;

            }
            return;
        }
        int len = r - l + 1;
        int mid = (r + l) / 2;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);

        int index = l;
        int ileft = l;
        int iright = mid + 1;
        while (ileft <= mid && iright <= r) {

            if (nums[ileft] > nums[iright]) {
                sortTemp[index++] = nums[iright];
                iright++;
            } else {
                sortTemp[index++] = nums[ileft];
                ileft++;
            }
        }

        while (iright <= r) {
            sortTemp[index++] = nums[iright];
            iright++;
        }

        while (ileft <= mid) {
            sortTemp[index++] = nums[ileft];
            ileft++;
        }

        for (int i = l; i <= r; i++) {
            nums[i] = sortTemp[i];
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
